// 给定一个二叉树和一个目标和，找到"所有"从根节点到叶子节点路径总和等于给定目标和的路径。

// 说明: 叶子节点是指没有子节点的节点。

// 暴露接口
function pathSum(root: TreeNode | null, sum: number): number[][] {
    const res: number[][] = [];
    const path: number[] = [];
    pathSum_DFS(root, sum, res, path);
    return res;
};

// 辅助深度优先遍历方法
function pathSum_DFS(root: TreeNode | null, sum: number,
    res: number[][], path: number[]) {
    // 递归出口--->安全检测
    if (root === null) {
        return;
    }
    // 将当前节点加入路径数组
    path.push(root.val);
    sum -= root.val;
    // 如果当前总和为零且遍历到根节点，将当前节点加入结果数组-->递归出口
    if (root.left === null && root.right === null) {
        if (sum === 0) {
            res.push(Array.from(path));
        }
        path.pop();
        return;
    }
    // 递归遍历左子树
    pathSum_DFS(root.left, sum, res, path);
    // 递归遍历右子树
    pathSum_DFS(root.right, sum, res, path);
    // 回溯部分
    path.pop();
}


// 这道题目又属于比较经典的深度优先遍历+回溯算法的标准问题
// 在递归的设计上要考虑的细节也是确实存在的
// sum的处理就比较常规，每入一轮次就减去当前的节点值
// 首先这道题目因为没有说明所有的节点值大于0，所以是不能剪枝操作的
// 然后递归的出口其实大部分情况是在叶节点处
// 当我们走到叶节点时，需要判断sum是否为0，为0的话就说明当前路径满足条件，直接加入结果数组
// 正常的每轮次中，我们每加入一个节点其实就应该判断此节点是否为叶节点（这里容易错）
// 此外回溯的部分中，也要额外注意回溯位置存在两处，
// 第一处是走到叶节点后，因为直接返回了所以需要回溯（状态重置）
// 第二处是递归完左右子树后，也需要做回溯（一条路径走完后逐步退回）